package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 分割等和子集
   static class Solution {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            int n = nums.length;
            for (int x : nums) sum += x;

            // 边界：sum为奇数，无法分割
            if (sum % 2 != 0) return false;

            int target = sum / 2;
            // dp[i][j]：前i个元素能否凑出和为j
            boolean[][] dp = new boolean[n + 1][target + 1];

            // 初始化：0个元素可凑出和为0
            dp[0][0] = true;

            // 填充DP表
            for (int i = 1; i <= n; i++) { // 遍历每个元素
                for (int j = 1; j <= target; j++) { // 遍历每个可能的和
                    // 不选第i个元素，继承前i-1个元素的状态
                    dp[i][j] = dp[i - 1][j];

                    // 选第i个元素（需j >= 当前元素值，且前i-1个元素能凑出j - 当前元素值）
                    if (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]]) {
                        dp[i][j] = true;
                    }
                }
            }

            // 前n个元素能否凑出target（即能否分割为两个等和子集）
            return dp[n][target];
        }
    }
}